/*
 * @lc app=leetcode.cn id=233 lang=cpp
 *
 * [233] 数字 1 的个数
 */

// [1, n]
// n= 345 [Y] 78
//    345 [1] xx

// (1) xxx [1] xx: xxx最大为344; xx最大为78
// 000   00
// 000   01
// ...   ..
// 344   99

// (2) 边界情况
// 345 * 100

// (2.1) digit > 1
// 345 => 1*100

// (2.2) digit == 1
// 345 => 1*79 (i.e. 00-78)

// (2.3) digit == 0
// 345 => 0

// @lc code=start
class Solution
{
 public:
  int countDigitOne(int n)
  {
    if (n < 0) return 0;

    int count = 0;
    string str = to_string(n);

    reverse(str.begin(), str.end());

    for (int i = 1; i <= str.size(); i++)
    {
      int a = n / (int)pow(10, i);
      count += a * (int)pow(10, i - 1);  // (1)

      int digit = str[i - 1] - '0';  // 字符转换成数值

      if (digit > 1)  // (2.1)
        count += pow(10, i - 1);
      else if (digit == 1)  // (2.2)
        count += n % (int)pow(10, i - 1) + 1;

      // (2.3)为0
    }

    return count;
  }
};
// @lc code=end
